package lsl.leetCode.year2023.test0202;

import lsl.leetCode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * description:二叉树的中序遍历:(根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面)
 *
 * @author: liushengli
 * data: 2023/2/2
 */
public class test94 {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNod2 = new TreeNode(2);
        TreeNode treeNod3 = new TreeNode(3);
        TreeNode treeNod4 = new TreeNode(4);
        TreeNode treeNod5 = new TreeNode(5);
        TreeNode treeNod6 = new TreeNode(6);
        TreeNode treeNod7 = new TreeNode(7);
        TreeNode treeNod8 = new TreeNode(8);
        TreeNode treeNod9 = new TreeNode(9);
        TreeNode treeNod10 = new TreeNode(10);
        treeNode1.left = treeNod2;
        treeNode1.right = treeNod3;
        treeNod3.left = treeNod10;
        treeNod2.left = treeNod4;
        treeNod2.right = treeNod5;
        treeNod4.left = treeNod6;
        treeNod4.right = treeNod7;
        treeNod7.left = treeNod8;
        treeNod7.right = treeNod9;
        inorderTraversal(treeNode1);
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        traversal(root, list);
        return list;
    }

    private static void traversal(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            traversal(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            traversal(root.right, list);
        }
    }
}
